HDU_5818

思路

Joint Stacks
比较简单巧妙的一个做法是引入一个新的栈C,每次合并的时候就把A和B合并到C上,然后把A和B都清空. push还是按正常做,pop注意当遇到要pop的栈为空时,因为题目保证不会对空栈进行pop操作,所以这时应直接改为对C栈进行pop操作. 这样做因为保证每个元素最多只在一次合并中被处理到,pop和push操作当然也是每个元素只做一次,所以总复杂度是O(N)的. 另一种做法是用链表来直接模拟,复杂度也是O(N),但代码量稍大一些.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define NV 100005
int aind,bind,C[2*NV],cind,pre;
struct mystly
{
int value,time;
}A[NV],B[NV];
bool ok[NV];
int main(){
int n,tmp,ca=0;char str[4];
/* freopen("1010.in","r",stdin);
freopen("myout.out","w",stdout);*/
while(scanf("%d",&n)){
if(n==0)break;
printf("Case #%d:\n",++ca);
aind=0,bind=0,cind=0;
for(int i=1 ;i<=n ;i++){
scanf("%s",str);
if(str[1]=='u'){
scanf("%s%d",str,&tmp);
if(str[0]=='A'){
A[++aind].time=i;
A[aind].value=tmp;
}
else{
B[++bind].time=i;
B[bind].value=tmp;
}
}
else if(str[1]=='o'){
scanf("%s",str);
if(str[0]=='A'){
if(aind>0){
printf("%d\n",A[aind--].value);
}
else{
printf("%d\n",C[cind--]);
}
}
else{
if(bind>0){
printf("%d\n",B[bind--].value);
}
else{
printf("%d\n",C[cind--]);
}
}
}
else if(str[1]=='e'){
scanf("%s%s",str,str);
int ii=1,jj=1;
while(ii<=aind && jj<=bind){
if(A[ii].time<B[jj].time){
C[++cind]=A[ii++].value;
}
else{
C[++cind]=B[jj++].value;
}
}
while(ii<=aind)C[++cind]=A[ii++].value;
while(jj<=bind)C[++cind]=B[jj++].value;
aind=0;bind=0;
}
}
}
return 0;
}